/**
https://leetcode-cn.com/problems/binary-tree-right-side-view/
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

    - stack.push(root)
    - 循环
        - node = stack.pop
        - stack.push node->left（栈底，出栈时【慢】访问）
        - stack.push node->right（栈顶，出栈时【先】访问）
*/

class Solution {
public:
    vector<int> rightSideView(TreeNode* root)
    {
        stack<TreeNode*> nodeStack;
        stack<int> depthStack;

        nodeStack.push(root); // 1. 压栈【1】树的【根节点】
        depthStack.push(0); // 2. 压栈【2】根节点 对应的【深度 0】

        // 3. 构造 map 存储【每一个深度】对应的【right 子节点】
        // - depth=0, 节点1
        // - depth=1, 节点3
        // - depth=2, 节点4
        unordered_map<int, int> hash;

        // 4. 记录【最大】深度
        int max_depth = 0;

        // 5. 不断的 pop stack
        while (!nodeStack.empty())
        {
            // 取出栈顶【元素】
            TreeNode* node = nodeStack.top();
            nodeStack.pop();

            // 取出退栈元素 对应的【深度】
            int depth = depthStack.top();
            depthStack.pop();

            if (!node)
                break;

            // 记录【更大深度】，用于后面 map => vector
            max_depth = max(max_depth, depth);

            // 如果 深度【不存在】对应的节点，才插入 节点->value
            if (hash.find(depth) == hash.end()) {
                hash[depth] =  node -> val;
            }

            // push left
            nodeStack.push(node -> left); // push【节点】
            depthStack.push(depth + 1); // push 节点对应的【深度】

            // push right
            nodeStack.push(node -> right);
            depthStack.push(depth + 1);
        }

        // map => vector
        vector<int> rightView;
        for (int depth = 0; depth <= max_depth; ++depth)
            rightView.push_back(hash[depth]); // 一次 push back 深度 对应的 节点

        return rightView;
    }
};
